package q64_minPathSum;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        int[][] arr1 = new int[][]{{1,2,3}, {4,5,6}};
        System.out.println(s.minPathSum(arr1));
    }

    public int minPathSum(int[][] grid) {
        int[][] f = new int[grid.length][grid[0].length];
        f[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; ++i) {
            f[i][0] = f[i - 1][0] + grid[i][0];
            // System.out.println(f[i][0]);
        }

        for (int j = 1; j < grid[0].length; ++j) {
            f[0][j] = f[0][j - 1] + grid[0][j];
            // System.out.println(f[0][j]);
        }

        // 到(i,j)这个点的最短路，相当于到(i - 1, j) , (i, j - 1)这两个点中最短路与当前格子值的和
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; ++j) {
                f[i][j] = Math.min(f[i - 1][j],f[i][j - 1]) + grid[i][j] ;
            }
        }

        // 得到答案
        return f[grid.length - 1][grid[0].length - 1];
    }
}
